package collection;

import java.util.Iterator;

public class HashTableMap<K, V> implements IMap<K, V> {

	Object[] internalArray = null;
	private int size = 0;
	
	public HashTableMap()
	{
		internalArray = new Object[2];
	}
	
	public HashTableMap(int arraySize)
	{
		this.internalArray = new Object[arraySize];
	}
	
	@Override
	public int size() 
	{
		return this.size;
	}

	@Override
	public boolean isEmpty() 
	{
		return this.size == 0;
	}
	
	private int compress(int hashCode, int length)
	{
		return hashCode % length;
	}
	
	private ListMap<K,V> findListMap(K key)
	{
		int index = compress(key.hashCode(), this.internalArray.length);
		ListMap<K,V> listMap = (ListMap<K, V>) this.internalArray[index];
		
		return listMap;
	}

	@Override
	public V get(K key) 
	{
		ListMap<K,V> listMap = findListMap(key);
		if (listMap != null)
		{
			return listMap.get(key);
		}
		else
		{
			return null;
		}
	}
	
	@Override
	public V remove(K key) 
	{
		ListMap<K,V> listMap = findListMap(key);
		if (listMap != null && !listMap.isEmpty())
		{
			this.size -= 1;
			return listMap.remove(key);
		}
		else
		{
			return null;
		}
	}
	
	private void rehash() 
	{
		int oldSize = this.internalArray.length * 2;
		int newSize = oldSize * 2;
		Object[] newArray = new Object[newSize];
		for (int i=0; i<this.internalArray.length; i++)
		{
			ListMap<K,V> listMap = (ListMap<K, V>) this.internalArray[i];
			if ( listMap != null)
			{
				for (Entry<K,V> entry : listMap)
				{
					K key = entry.getKey();
					V value = entry.getValue();
					int newIndex = compress(key.hashCode(), newSize);
					ListMap<K,V> newListMap = (ListMap<K, V>) newArray[newIndex];
					if (newListMap == null)
					{
						newListMap = new ListMap<K,V>();
						newArray[newIndex] = newListMap;
					}
					newListMap.put(key, value);
				}
			}
		}
		this.internalArray = newArray;
	}

	@Override
	public void put(K key, V value) 
	{
		int index = compress(key.hashCode(), this.internalArray.length);
		ListMap<K,V> listMap = (ListMap<K, V>) this.internalArray[index];
		
		if (listMap == null)
		{
			listMap = new ListMap<K,V>();
			this.internalArray[index] = listMap;
		}
		
		this.size -= listMap.size();
		listMap.put(key, value);
		this.size += listMap.size();
		
		if ((this.size / this.internalArray.length * 1.0) >= 2)
		{
			rehash();
		}
	}

	@Override
	public Iterator<K> keys() 
	{
		final Iterator<Entry<K,V>> entryIter = entries();
		
		return new Iterator<K>(){

			@Override
			public boolean hasNext() 
			{
				return entryIter.hasNext();
			}

			@Override
			public K next() 
			{
				return entryIter.next().getKey();
			}

			@Override
			public void remove() 
			{
				throw new UnsupportedOperationException();
			}
			
		};
	}

	@Override
	public Iterator<V> values()
	{
		final Iterator<Entry<K,V>> entryIter = entries();
		
		return new Iterator<V>(){

			@Override
			public boolean hasNext() 
			{
				return entryIter.hasNext();
			}

			@Override
			public V next() 
			{
				return entryIter.next().getValue();
			}

			@Override
			public void remove() 
			{
				throw new UnsupportedOperationException();
			}
			
		};
	}

	@Override
	public Iterator<Entry<K, V>> entries() 
	{
		return new HashTableIterator<Entry<K,V>>(this);
	}

	@Override
	public Iterator<Entry<K, V>> iterator() 
	{
		return entries();
	}

	private class HashTableIterator<E> implements Iterator<Entry<K,V>>{

		HashTableMap<K,V> hashTableMap;
		SLinkedList<Iterator<Entry<K,V>>> iterList;
		MergedIterator<Entry<K,V>> mergedIter;
		
		HashTableIterator(HashTableMap<K,V> hashTableMap)
		{
			this.hashTableMap = hashTableMap;
			this.iterList = new SLinkedList<Iterator<Entry<K,V>>>();
			for (int i = 0; i < this.hashTableMap.internalArray.length; i++)
			{
				ListMap<K,V> listMap = (ListMap<K, V>) this.hashTableMap.internalArray[i];
				if (listMap != null)
				{
					iterList.addLast(iterList.createNode(listMap.entries()));
				}
			}
			this.mergedIter = new MergedIterator<Entry<K,V>>(iterList);
		}
		
		@Override
		public boolean hasNext() 
		{
			return this.mergedIter.hasNext();
		}

		@Override
		public Entry<K, V> next() 
		{
			return this.mergedIter.next();
		}

		@Override
		public void remove() 
		{
			throw new UnsupportedOperationException();
		}
		
	}
}

